from collections import defaultdict
from typing import List


class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        ew = defaultdict(int)
        for w in p:
            ew[w] += 1
        
        epart = defaultdict(int)
        result = []

        for i in range(len(p)):
            if s[i] in ew:
                epart[s[i]] += 1
        
        if epart == ew:
            result.append(0)

        # 主循环部分
        for i in range(1,len(s)-len(p)):
            if s[i-1] in ew:
                epart[s[i-1]] -= 1
            end_index = i+len(p)-1
            if s[end_index] in ew:
                epart[s[end_index]] += 1
            if epart==ew:
                result.append(i)
        
        return result
    
if __name__ == "__main__":
    s = Solution()
    r = s.findAnagrams(s = "cbaebabacd", p = "abc")
    print(r)
        
